package day9;

import java.util.HashMap;

public class code4 {


    public static int h;
    public static int t;
    public int pathSum(TreeNode root, int targetSum) {
        h = 0;
        t = targetSum;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);


        return h;
    }


    public void fun(TreeNode node,HashMap<Integer,Integer> map,int sum){
        if(node==null){return;}
        map.put(sum+node.val,map.getOrDefault(sum+node.val,0)+1);
        h += map.getOrDefault(node.val+sum-t,0);

        fun(node.left,map,sum+node.val);
        fun(node.right,map,sum+node.val);

        map.put(sum+node.val,map.get(sum+node.val)-1);

    }


    public static TreeNode result;
    public static boolean falg;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        falg = true;
        fun1(root,p,q);
        return result;

    }


    public TreeNode fun1(TreeNode node,TreeNode p,TreeNode q){
        if(node==null) return null;

        TreeNode lt = fun1(node.left,p,q);
        TreeNode rt = fun1(node.right,p,q);

        if((lt==p&&rt==q)||(rt==p||lt==q)){
            if(falg){
                result = node;
                falg = false;
            }
        }

        if (node == p && (lt == q || rt == q)) {
            if(falg){
                result = node;
                falg = false;
            }
        }

        if(node == q && (lt == p|| rt == p)){
            if(falg){
                result = node;
                falg = false;
            }
        }


        if(node==p||node==q) return node;
        return null;


    }



    public static int max;

    public int maxPathSum(TreeNode root) {

        max = -200;
        fun3(root);
        return max;

    }

    public int fun3(TreeNode node){
        if(node==null) return 0;

        int lt = fun3(node.left);
        int rt = fun3(node.right);

        int num = Math.max(lt,rt);
        num = Math.max(num,rt+lt);
        num = Math.max(node.val,num+node.val);
        max = Math.max(max,num);

        int n = Math.max(lt,rt);
        return Math.max(node.val+n,n);


    }






}
